null
(Ed.)
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we initiate the study of a thresholded version of the problem: for a given parameter $c$, find a smaller graph, which we call \emph{connectivity-$c$ mimicking network}, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that connectivity-$c$ mimicking networks of size $O(kc^4)$ exist and can be found in time $m(c\log n)^{O(c)}$. We also give a separate algorithm that constructs such graphs of size $k \cdot O(c)^{2c}$ in time $mc^{O(c)}\log^{O(1)}n$.
These results lead to the first offline data structures for answering fully dynamic $c$-edge-connectivity queries for $c \ge 4$ in polylogarithmic time per query as well as more efficient algorithms for survivable network design on bounded treewidth graphs.
more »
« less
